When designing integrated circuits, logic is often required to perform addition, subtraction, multiplication and division. Whilst addition, subtraction and multiplication operations can all be cheaply implemented (e.g. in terms of area of logic required) in hardware, division operations are acknowledged to be an expensive operation to implement in hardware.
In the case that the divisor is known to be a constant at design-time, a division operation can be expressed as multiplication by a constant fraction (also referred to as an ‘invariant rational’) and it is possible to construct efficient implementations of the division operation using a combination of addition and constant multiplication logic. This can simplify the logic significantly and hence reduce the area of integrated circuit needed to implement the division operation.
In various examples, the result from a division operation need not be calculated accurately but instead the result can be rounded to the nearest integer or otherwise approximated; however, in many examples, the error, ε, in the result (as defined as the difference between the accurate result R and the result generated R′) needs to satisfy an error bound, εmax, i.e.ε=R−R′|ε|≤εmax This approximate calculation of a division operation may be referred to as ‘lossy constant division’.
The embodiments described below are provided by way of example only and are not limiting of implementations which solve any or all of the disadvantages of known methods and hardware for implementing lossy constant division.